/*
 * @Author: szx
 * @Date: 2022-03-24 15:35:47
 * @LastEditTime: 2022-03-24 16:06:52
 * @Description:
 * @FilePath: \leetcode\剑指offer\40\40.js
 */
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getLeastNumbers = function (arr, k) {
    arr.sort((a, b) => a - b);
    return arr[k];
};

var getLeastNumbers = function (arr, k) {
    const n = arr.length;
    const quickSort = (arr, left = 0, right = n - 1) => {
        if (left >= right) return;
        let l = left,
            r = right;
        while (l < r) {
            while (l < r && arr[r] >= arr[left]) r--;
            while (l < r && arr[l] <= arr[left]) l++;
            swap(arr, l, r);
        }
        swap(arr, l, left);
        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    };
    return;
};
var swap = function (arr, i, j) {
    let tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
};

var getLeastNumbers = function (arr, k) {
    const quickSort = (arr, left = 0, right = n - 1) => {
        if (left >= right) return right;
        const pivot = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= pivot) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= pivot) left++;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    };
    const n = arr.length;
    let start = 0;
    let end = n - 1;
    // 寻找一次标杆元素的位置
    let index = quickSort(arr, start, end);
    while (index !== k - 1) {
        if (index > k - 1) {
            end = index - 1;
        } else {
            start = index + 1;
        }
        index = quickSort(arr, start, end);
    }
    return arr.slice(0, k);
};
console.log(getLeastNumbers([0, 0, 0, 2, 0, 5], 0));
console.log(getLeastNumbers([3, 2, 1], 2));
console.log(getLeastNumbers([0, 1, 2, 1], 1));
